{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count The Repetitions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMaxRepetitions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计重复个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>定义 <code>str = [s, n]</code> 表示 <code>str</code> 由 <code>n</code> 个字符串 <code>s</code> 连接构成。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>str == [\"abc\", 3] ==\"abcabcabc\"</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果可以从 <code>s2</code><sub> </sub>中删除某些字符使其变为 <code>s1</code>，则称字符串 <code>s1</code><sub> </sub>可以从字符串 <code>s2</code> 获得。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，根据定义，<code>s1 = \"abc\"</code> 可以从 <code>s2 = \"ab<em><strong>dbe</strong></em>c\"</code> 获得，仅需要删除加粗且用斜体标识的字符。</li>\n",
    "</ul>\n",
    "\n",
    "<p>现在给你两个字符串 <code>s1</code> 和 <code>s2</code> 和两个整数 <code>n1</code> 和 <code>n2</code> 。由此构造得到两个字符串，其中 <code>str1 = [s1, n1]</code>、<code>str2 = [s2, n2]</code> 。</p>\n",
    "\n",
    "<p>请你找出一个最大整数 <code>m</code> ，以满足 <code>str = [str2, m]</code> 可以从 <code>str1</code> 获得。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"acb\", n1 = 4, s2 = \"ab\", n2 = 2\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"acb\", n1 = 1, s2 = \"acb\", n2 = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s1.length, s2.length <= 100</code></li>\n",
    "\t<li><code>s1</code> 和 <code>s2</code> 由小写英文字母组成</li>\n",
    "\t<li><code>1 <= n1, n2 <= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-the-repetitions](https://leetcode.cn/problems/count-the-repetitions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-the-repetitions](https://leetcode.cn/problems/count-the-repetitions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"acb\"\\n4\\n\"ab\"\\n2', '\"acb\"\\n1\\n\"acb\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        dp=[]\n",
    "        for i in range(len(s2)):\n",
    "            start=i\n",
    "            end=0\n",
    "            for j in range(len(s1)):\n",
    "                if s1[j] == s2[start]:\n",
    "                    start+=1\n",
    "                    if start==len(s2):\n",
    "                        start=0\n",
    "                        end+=1\n",
    "            dp.append((start,end))\n",
    "        res=0\n",
    "        next=0\n",
    "        for _ in range(n1):\n",
    "            res+=dp[next][1]\n",
    "            next=dp[next][0]\n",
    "        return res//n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "            s1_cnt, s2_cnt, index = 0,0,0\n",
    "            recall = dict()\n",
    "            while True:\n",
    "                s1_cnt += 1\n",
    "                for ch in s1:\n",
    "                    if ch == s2[index]:\n",
    "                        index += 1\n",
    "                        if index == len(s2):\n",
    "                            index, s2_cnt = 0, s2_cnt +1\n",
    "                if s1_cnt == n1:\n",
    "                    return s2_cnt // n2\n",
    "                if index in recall:\n",
    "                    s1_cnt_prime, s2_cnt_prime = recall[index]\n",
    "                    in_loop = [s1_cnt-s1_cnt_prime, s2_cnt- s2_cnt_prime]\n",
    "                    break\n",
    "                else:\n",
    "                    recall[index] = s1_cnt, s2_cnt                   \n",
    "\n",
    "            ans  = s2_cnt_prime + (n1 - s1_cnt_prime) // in_loop[0] * in_loop[1]\n",
    "            print(recall)\n",
    "\n",
    "\n",
    "            rest = (n1 - s1_cnt_prime)%in_loop[0]\n",
    "            for i in range(rest):\n",
    "                for ch in s1:\n",
    "                    if ch == s2[index]:\n",
    "                        index += 1\n",
    "                        if index == len(s2):\n",
    "                            ans += 1\n",
    "                            index = 0 \n",
    "            return ans//n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        records = []  # records 内部存储一对一对的数字，分别记录从s2的某一位i开始,s1可以对s2[i:]匹配几次和当s1走完s2下一次应该从哪一个位置开始遍历\n",
    "\n",
    "        for i in range(len(s2)):\n",
    "            next_pos = i\n",
    "            count_s1 = 0\n",
    "            for j in range(len(s1)):\n",
    "                if s1[j] == s2[next_pos]:  # 如果s1某一位匹配上s2某一位\n",
    "                    next_pos += 1\n",
    "                if next_pos == len(s2):  # next_pos更新后立刻判断是否达到s2边界\n",
    "                    next_pos = 0\n",
    "                    count_s1 += 1\n",
    "            records.append([count_s1, next_pos])  # 将一对一对的数据压入\n",
    "\n",
    "        res, next_pos = 0, 0\n",
    "        for _ in range(n1):  # 最后这一步也就是求有n1个s1最终能匹配多少\n",
    "            res += records[next_pos][0]\n",
    "            next_pos = records[next_pos][1]\n",
    "        return res // n2  # 因为最终是求能匹配多少个S2，所以除n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        if n1 == 0:\n",
    "            return 0\n",
    "        s1cnt, index, s2cnt = 0, 0, 0\n",
    "        recall = dict()\n",
    "        while True:\n",
    "            s1cnt += 1\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        s2cnt, index = s2cnt + 1, 0\n",
    "            if s1cnt == n1:\n",
    "                return s2cnt // n2\n",
    "            if index in recall:\n",
    "                s1cnt_prime, s2cnt_prime = recall[index]\n",
    "                pre_loop = (s1cnt_prime, s2cnt_prime)\n",
    "                in_loop = (s1cnt - s1cnt_prime, s2cnt - s2cnt_prime)\n",
    "                break\n",
    "            else:\n",
    "                recall[index] = (s1cnt, s2cnt)\n",
    "        \n",
    "        ans = pre_loop[1] + (n1 - pre_loop[0]) // in_loop[0] * in_loop[1]\n",
    "        rest = (n1 - pre_loop[0]) % in_loop[0]\n",
    "        for i in range(rest):\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        ans, index = ans + 1, 0\n",
    "        return ans // n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        '''\n",
    "        10/12 动态规划算法\n",
    "        对齐索引，s2里的元素和s1里单个进行匹配，如果到结尾则开始循环\n",
    "        s1中最多有多少s2\n",
    "        10/22 review 状态转移\n",
    "        '''\n",
    "        # 遍历s2中的每个元素，在s1里找对应的 end用于计数匹配次数\n",
    "        # 当遍历到s2的末尾，就回到s2的最前继续找，直到整个s2遍历完成\n",
    "        # dp[i]表示s1和s2[i]作为开头匹配时，下一个循环的s1会和s2的哪个索引作为开头匹配，同时也存储了能匹配到几个s2的末尾。\n",
    "        dp=[]\n",
    "        for i in range(len(s2)):\n",
    "            start = i \n",
    "            end = 0\n",
    "            for j in range(len(s1)):\n",
    "                if s1[j] == s2[start]:\n",
    "                    start += 1\n",
    "                if start == len(s2):\n",
    "                    start = 0 \n",
    "                    end +=1 \n",
    "            dp.append((start, end))\n",
    "        res=0\n",
    "        next=0\n",
    "        for _ in range(n1):\n",
    "            res+=dp[next][1]\n",
    "            next=dp[next][0]\n",
    "        return res//n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        # s1cnt 保存经历了多少个s1，index保存当前s2的位置索引，s2cnt保存成功匹配了多少个s2\n",
    "        # 用dict保存index存在的s1cnt和s2cnt\n",
    "        # 如果存在了index，那么cur_s1cnt - pre_s1cnt个s1中可以匹配成功cur_s2cnt-pre_s2cnt\n",
    "        # 通过公式的方式可以计算出优多少个cnt个s2，然后除以n2就是要求的m\n",
    "        # 但是存在剩余rest个s1中，还需要匹配s2。\n",
    "        if n1==0: return 0\n",
    "        s1cnt, index, s2cnt = 0, 0, 0\n",
    "        n, m = len(s1), len(s2)\n",
    "        index_mps = {}\n",
    "        while True:\n",
    "            s1cnt += 1\n",
    "            for i in range(n):\n",
    "                if s1[i]==s2[index]:\n",
    "                    index += 1\n",
    "                    if index == m:\n",
    "                        s2cnt, index = s2cnt + 1, 0\n",
    "            if s1cnt == n1:\n",
    "                return s2cnt//n2 \n",
    "            if index in index_mps:\n",
    "                pre_s1cnt, pre_s2cnt = index_mps[index]\n",
    "                # pre_loop = (pre_s1cnt, pre_s2cnt)\n",
    "                in_loop = (s1cnt-pre_s1cnt, s2cnt-pre_s2cnt)\n",
    "                break\n",
    "            else:\n",
    "                index_mps[index] = (s1cnt, s2cnt)\n",
    "        res = pre_s2cnt + (n1-pre_s1cnt)//in_loop[0] * in_loop[1]\n",
    "        rest = (n1-pre_s1cnt) % in_loop[0]\n",
    "        # index = 0\n",
    "        for i in range(rest):\n",
    "            for c in s1:\n",
    "                if c==s2[index]:\n",
    "                    index += 1\n",
    "                    if index==m:\n",
    "                        res += 1\n",
    "                        index = 0\n",
    "        return res // n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        n = len(s2)\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            j = i\n",
    "            for c in s1:\n",
    "                if c == s2[j]:\n",
    "                    j += 1\n",
    "                if j == n:\n",
    "                    cnt += 1\n",
    "                    j = 0\n",
    "            d[i] = (cnt, j)\n",
    "\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for _ in range(n1):\n",
    "            cnt, j = d[j]\n",
    "            ans += cnt\n",
    "        return ans // n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        if n1 == 0:\n",
    "            return 0\n",
    "        s1cnt, index, s2cnt = 0, 0, 0\n",
    "        # recall 是我们用来找循环节的变量，它是一个哈希映射\n",
    "        # 我们如何找循环节？假设我们遍历了 s1cnt 个 s1，此时匹配到了第 s2cnt 个 s2 中的第 index 个字符\n",
    "        # 如果我们之前遍历了 s1cnt' 个 s1 时，匹配到的是第 s2cnt' 个 s2 中同样的第 index 个字符，那么就有循环节了\n",
    "        # 我们用 (s1cnt', s2cnt', index) 和 (s1cnt, s2cnt, index) 表示两次包含相同 index 的匹配结果\n",
    "        # 那么哈希映射中的键就是 index，值就是 (s1cnt', s2cnt') 这个二元组\n",
    "        # 循环节就是；\n",
    "        #    - 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2\n",
    "        #    - 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2\n",
    "        # 那么还会剩下 (n1 - s1cnt') % (s1cnt - s1cnt') 个 s1, 我们对这些与 s2 进行暴力匹配\n",
    "        # 注意 s2 要从第 index 个字符开始匹配\n",
    "        recall = dict()\n",
    "        while True:\n",
    "            # 我们多遍历一个 s1，看看能不能找到循环节\n",
    "            s1cnt += 1\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        s2cnt, index = s2cnt + 1, 0\n",
    "            # 还没有找到循环节，所有的 s1 就用完了\n",
    "            if s1cnt == n1:\n",
    "                return s2cnt // n2\n",
    "            # 出现了之前的 index，表示找到了循环节\n",
    "            if index in recall:\n",
    "                s1cnt_prime, s2cnt_prime = recall[index]\n",
    "                # 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2\n",
    "                pre_loop = (s1cnt_prime, s2cnt_prime)\n",
    "                # 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2\n",
    "                in_loop = (s1cnt - s1cnt_prime, s2cnt - s2cnt_prime)\n",
    "                break\n",
    "            else:\n",
    "                recall[index] = (s1cnt, s2cnt)\n",
    "\n",
    "        # ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 pre_loop 和 in_loop\n",
    "        ans = pre_loop[1] + (n1 - pre_loop[0]) // in_loop[0] * in_loop[1]\n",
    "        # S1 的末尾还剩下一些 s1，我们暴力进行匹配\n",
    "        rest = (n1 - pre_loop[0]) % in_loop[0]\n",
    "        for i in range(rest):\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        ans, index = ans + 1, 0\n",
    "        # S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2\n",
    "        return ans // n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        dp=[]\n",
    "        for i in range(len(s2)):\n",
    "            start=i\n",
    "            end=0\n",
    "            for j in range(len(s1)):\n",
    "                if s1[j] == s2[start]:\n",
    "                    start+=1\n",
    "                    if start==len(s2):\n",
    "                        start=0\n",
    "                        end+=1\n",
    "            dp.append((start,end))\n",
    "        print(dp)\n",
    "        res=0\n",
    "        next=0\n",
    "        for _ in range(n1):\n",
    "            res+=dp[next][1]\n",
    "            next=dp[next][0]\n",
    "        return res//n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        # 预处理\n",
    "        charset = set(s2)\n",
    "        array1 = []\n",
    "        for char in s1:\n",
    "            if char in charset:\n",
    "                array1.append(char)\n",
    "        array2 = list(s2)\n",
    "        loop1, loop2 = 0, 0\n",
    "        j = 0\n",
    "        recordloop = {}\n",
    "        for _ in range(n1):\n",
    "            for i in range(len(array1)):\n",
    "                if array1[i] == array2[j]:\n",
    "                    j += 1\n",
    "                    if j == len(array2):\n",
    "                        loop2 += 1\n",
    "                        j = 0\n",
    "            loop1 += 1\n",
    "            if j in recordloop:\n",
    "                preloop = recordloop[j]\n",
    "                loop = (loop1 - preloop[0], loop2 - preloop[1])\n",
    "                break\n",
    "            else:\n",
    "                recordloop[j] = (loop1, loop2)\n",
    "        \n",
    "        if loop1 == n1:\n",
    "            return loop2 // n2\n",
    "        \n",
    "        ans = preloop[1] + (n1 - preloop[0]) // loop[0] * loop[1]\n",
    "        remain = (n1 - preloop[0]) % loop[0]\n",
    "\n",
    "        for _ in range(remain):\n",
    "            for char in array1:\n",
    "                if char == array2[j]:\n",
    "                    j += 1\n",
    "                    if j == len(array2):\n",
    "                        ans += 1\n",
    "                        j = 0\n",
    "        \n",
    "        return ans // n2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        if n1 == 0:\n",
    "            return 0\n",
    "        s1cnt, index, s2cnt = 0, 0, 0\n",
    "        # recall 是我们用来找循环节的变量，它是一个哈希映射\n",
    "        # 我们如何找循环节？假设我们遍历了 s1cnt 个 s1，此时匹配到了第 s2cnt 个 s2 中的第 index 个字符\n",
    "        # 如果我们之前遍历了 s1cnt' 个 s1 时，匹配到的是第 s2cnt' 个 s2 中同样的第 index 个字符，那么就有循环节了\n",
    "        # 我们用 (s1cnt', s2cnt', index) 和 (s1cnt, s2cnt, index) 表示两次包含相同 index 的匹配结果\n",
    "        # 那么哈希映射中的键就是 index，值就是 (s1cnt', s2cnt') 这个二元组\n",
    "        # 循环节就是；\n",
    "        #    - 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2\n",
    "        #    - 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2\n",
    "        # 那么还会剩下 (n1 - s1cnt') % (s1cnt - s1cnt') 个 s1, 我们对这些与 s2 进行暴力匹配\n",
    "        # 注意 s2 要从第 index 个字符开始匹配\n",
    "        recall = dict()\n",
    "        while True:\n",
    "            # 我们多遍历一个 s1，看看能不能找到循环节\n",
    "            s1cnt += 1\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        s2cnt, index = s2cnt + 1, 0\n",
    "            # 还没有找到循环节，所有的 s1 就用完了\n",
    "            if s1cnt == n1:\n",
    "                return s2cnt // n2\n",
    "            # 出现了之前的 index，表示找到了循环节\n",
    "            if index in recall:\n",
    "                s1cnt_prime, s2cnt_prime = recall[index]\n",
    "                # 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2\n",
    "                pre_loop = (s1cnt_prime, s2cnt_prime)\n",
    "                # 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2\n",
    "                in_loop = (s1cnt - s1cnt_prime, s2cnt - s2cnt_prime)\n",
    "                break\n",
    "            else:\n",
    "                recall[index] = (s1cnt, s2cnt)\n",
    "\n",
    "        # ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 pre_loop 和 in_loop\n",
    "        ans = pre_loop[1] + (n1 - pre_loop[0]) // in_loop[0] * in_loop[1]\n",
    "        # S1 的末尾还剩下一些 s1，我们暴力进行匹配\n",
    "        rest = (n1 - pre_loop[0]) % in_loop[0]\n",
    "        for i in range(rest):\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        ans, index = ans + 1, 0\n",
    "        # S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2\n",
    "        return ans // n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\r\n",
    "        l1,l2 = len(s1),len(s2)\r\n",
    "        p1,p2 = 0,0\r\n",
    "        m1,m2 = 0,0\r\n",
    "        flags = []\r\n",
    "        begin = True\r\n",
    "        loopcheck = False\r\n",
    "        while m1 < n1:\r\n",
    "            if s1[p1]==s2[p2]:\r\n",
    "                if (not loopcheck) and begin:\r\n",
    "                    for item in flags:\r\n",
    "                        if item[0]==(p1,p2):\r\n",
    "                            loopcheck = True\r\n",
    "                            loop_len = m1-item[1][0]\r\n",
    "                            n2len = m2-item[1][1]\r\n",
    "                            #print(item,m1,m2,loop_len,n2len)\r\n",
    "                            loops = int((n1-m1)/loop_len)-1\r\n",
    "                            m1 += loops*loop_len\r\n",
    "                            m2 += loops*n2len\r\n",
    "                            #print(m1,m2)\r\n",
    "                            break\r\n",
    "                    flags.append(((p1,p2),(m1,m2)))\r\n",
    "                    begin = False\r\n",
    "                p1 += 1\r\n",
    "                p2 += 1\r\n",
    "            else:\r\n",
    "                p1 += 1\r\n",
    "            if p1>=l1:\r\n",
    "                p1 = 0\r\n",
    "                begin = True\r\n",
    "                m1 += 1\r\n",
    "            if p2>=l2:\r\n",
    "                p2 = 0\r\n",
    "                m2 += 1\r\n",
    "        #print(m1,m2,p1,p2)\r\n",
    "        #print(loop_len,n2len)\r\n",
    "        return int(m2/n2)\r\n",
    "        \r\n",
    "            \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "\n",
    "        len1, len2 = len(s1), len(s2)\n",
    "        index1, index2 = 0, 0\n",
    "\n",
    "        if len1 == 0 or len2 == 0 or len1 * n1 < len2 * n2:\n",
    "            return 0\n",
    "\n",
    "        map1, map2 = {}, {}\n",
    "        ans = 0\n",
    "\n",
    "        while index1 // len1 < n1:\n",
    "            if index1 % len1 == len1 - 1:\n",
    "                if index2 % len2 in map1:\n",
    "                    cycle_len = (index1 - map1[index2 % len2]) // len1\n",
    "                    cycle_num = (n1 - (index1 + 1) // len1) // cycle_len\n",
    "                    cycle_s2_num = (index2 - map2[index2 % len2]) // len2\n",
    "\n",
    "                    index1 += cycle_num * cycle_len * len1\n",
    "                    index2 += cycle_num * cycle_s2_num * len2\n",
    "                    ans += cycle_num * cycle_s2_num\n",
    "                else:\n",
    "                    map1[index2 % len2] = index1\n",
    "                    map2[index2 % len2] = index2\n",
    "\n",
    "            if s1[index1 % len1] == s2[index2 % len2]:\n",
    "                if index2 % len2 == len2 - 1:\n",
    "                    ans += 1\n",
    "                index2 += 1\n",
    "            index1 += 1\n",
    "        return ans // n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        #看s1中有多少个s2即可\n",
    "        list1=[]\n",
    "        for i in range(len(s2)):\n",
    "        #以s2的第一个元素的下标开始对齐，然后第二个，直到最后一个\n",
    "            start=i\n",
    "            end=0\n",
    "            for j in range(len(s1)):\n",
    "                if s1[j]==s2[start]:\n",
    "                    start+=1\n",
    "                    if start==len(s2):\n",
    "                        start=0\n",
    "                        end+=1\n",
    "            list1.append((start,end))\n",
    "        res=0\n",
    "        next=0\n",
    "        for _ in range(n1):\n",
    "            res+=list1[next][1]\n",
    "            next=list1[next][0]\n",
    "        return res//n2\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        if n1 == 0:\n",
    "            return 0\n",
    "        s1cnt, index, s2cnt = 0, 0, 0\n",
    "        # recall 是我们用来找循环节的变量，它是一个哈希映射\n",
    "        # 我们如何找循环节？假设我们遍历了 s1cnt 个 s1，此时匹配到了第 s2cnt 个 s2 中的第 index 个字符\n",
    "        # 如果我们之前遍历了 s1cnt' 个 s1 时，匹配到的是第 s2cnt' 个 s2 中同样的第 index 个字符，那么就有循环节了\n",
    "        # 我们用 (s1cnt', s2cnt', index) 和 (s1cnt, s2cnt, index) 表示两次包含相同 index 的匹配结果\n",
    "        # 那么哈希映射中的键就是 index，值就是 (s1cnt', s2cnt') 这个二元组\n",
    "        # 循环节就是；\n",
    "        #    - 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2\n",
    "        #    - 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2\n",
    "        # 那么还会剩下 (n1 - s1cnt') % (s1cnt - s1cnt') 个 s1, 我们对这些与 s2 进行暴力匹配\n",
    "        # 注意 s2 要从第 index 个字符开始匹配\n",
    "        recall = dict()\n",
    "        while True:\n",
    "            # 我们多遍历一个 s1，看看能不能找到循环节\n",
    "            s1cnt += 1\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        s2cnt, index = s2cnt + 1, 0\n",
    "            # 还没有找到循环节，所有的 s1 就用完了\n",
    "            if s1cnt == n1:\n",
    "                return s2cnt // n2\n",
    "            # 出现了之前的 index，表示找到了循环节\n",
    "            if index in recall:\n",
    "                s1cnt_prime, s2cnt_prime = recall[index]\n",
    "                # 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2\n",
    "                pre_loop = (s1cnt_prime, s2cnt_prime)\n",
    "                # 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2\n",
    "                in_loop = (s1cnt - s1cnt_prime, s2cnt - s2cnt_prime)\n",
    "                break\n",
    "            else:\n",
    "                recall[index] = (s1cnt, s2cnt)\n",
    "\n",
    "        # ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 pre_loop 和 in_loop\n",
    "        ans = pre_loop[1] + (n1 - pre_loop[0]) // in_loop[0] * in_loop[1]\n",
    "        # S1 的末尾还剩下一些 s1，我们暴力进行匹配\n",
    "        rest = (n1 - pre_loop[0]) % in_loop[0]\n",
    "        for i in range(rest):\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        ans, index = ans + 1, 0\n",
    "        # S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2\n",
    "        return ans // n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        lst=[]\n",
    "        ans=[]\n",
    "        n=len(s2)\n",
    "        s1=[i for i in s1 if i in s2]\n",
    "        cur=0\n",
    "        res=0\n",
    "        while True:\n",
    "            for i in s1:\n",
    "                if i==s2[cur%n]:\n",
    "                    cur+=1\n",
    "                    res+=1\n",
    "            if cur%n not in lst:\n",
    "                lst.append(cur%n)\n",
    "                ans.append(res)\n",
    "            else:\n",
    "                lst.append(cur%n)\n",
    "                ans.append(res)\n",
    "                break\n",
    "        t=lst.index(cur%n)\n",
    "        final=ans[t]\n",
    "        divide=len(lst)-t-1\n",
    "        shang,yushu=(n1-t-1)//divide,(n1-t-1)%divide\n",
    "        final+=(ans[-1]-ans[t])*shang+ans[t+yushu]-ans[t]\n",
    "        return final//len(s2)//n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "\n",
    "        len1, len2 = len(s1), len(s2)\n",
    "        index1, index2 = 0, 0\n",
    "\n",
    "        if len1 == 0 or len2 == 0 or len1 * n1 < len2 * n2:\n",
    "            return 0\n",
    "\n",
    "        map1, map2 = {}, {}\n",
    "        ans = 0\n",
    "\n",
    "        while index1 // len1 < n1:\n",
    "            if index1 % len1 == len1 - 1:\n",
    "                if index2 % len2 in map1:\n",
    "                    cycle_len = index1 // len1 - map1[index2 % len2] // len1\n",
    "                    cycle_num = (n1 - (index1 + 1) // len1) // cycle_len\n",
    "                    cycle_s2_num = index2 // len2 - map2[index2 % len2] // len2\n",
    "\n",
    "                    index1 += cycle_num * cycle_len * len1\n",
    "                    ans += cycle_num * cycle_s2_num\n",
    "                else:\n",
    "                    map1[index2 % len2] = index1\n",
    "                    map2[index2 % len2] = index2\n",
    "\n",
    "            if s1[index1 % len1] == s2[index2 % len2]:\n",
    "                if index2 % len2 == len2 - 1:\n",
    "                    ans += 1\n",
    "                index2 += 1\n",
    "            index1 += 1\n",
    "        return ans // n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        if n1 == 0:\n",
    "            return 0\n",
    "\n",
    "        cnt1, cnt2, index = 0,0,0\n",
    "        recall = dict()\n",
    "        while True: \n",
    "            cnt1 += 1\n",
    "            for w in s1:\n",
    "                if w == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        index = 0\n",
    "                        cnt2 += 1\n",
    "            if cnt1 == n1:\n",
    "                return cnt2 // n2\n",
    "            if index not in recall:\n",
    "                recall[index] = (cnt1, cnt2)\n",
    "            else:\n",
    "                precnt1, precnt2 = recall[index]\n",
    "                incnt1, incnt2 = cnt1-precnt1, cnt2-precnt2\n",
    "                break\n",
    "        \n",
    "        ans = precnt2 + (n1 - precnt1) // incnt1 * incnt2\n",
    "\n",
    "        rest = (n1 - precnt1) % incnt1\n",
    "\n",
    "        for i in range(rest):\n",
    "            for w in s1:\n",
    "                if w == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        index = 0\n",
    "                        ans += 1\n",
    "        return ans // n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        if n1 == 0:\n",
    "            return 0\n",
    "        s1cnt, index, s2cnt = 0, 0, 0\n",
    "        # recall 是我们用来找循环节的变量，它是一个哈希映射\n",
    "        # 我们如何找循环节？假设我们遍历了 s1cnt 个 s1，此时匹配到了第 s2cnt 个 s2 中的第 index 个字符\n",
    "        # 如果我们之前遍历了 s1cnt' 个 s1 时，匹配到的是第 s2cnt' 个 s2 中同样的第 index 个字符，那么就有循环节了\n",
    "        # 我们用 (s1cnt', s2cnt', index) 和 (s1cnt, s2cnt, index) 表示两次包含相同 index 的匹配结果\n",
    "        # 那么哈希映射中的键就是 index，值就是 (s1cnt', s2cnt') 这个二元组\n",
    "        # 循环节就是；\n",
    "        #    - 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2\n",
    "        #    - 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2\n",
    "        # 那么还会剩下 (n1 - s1cnt') % (s1cnt - s1cnt') 个 s1, 我们对这些与 s2 进行暴力匹配\n",
    "        # 注意 s2 要从第 index 个字符开始匹配\n",
    "        recall = dict()\n",
    "        while True:\n",
    "            # 我们多遍历一个 s1，看看能不能找到循环节\n",
    "            s1cnt += 1\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        s2cnt, index = s2cnt + 1, 0\n",
    "            # 还没有找到循环节，所有的 s1 就用完了\n",
    "            if s1cnt == n1:\n",
    "                return s2cnt // n2\n",
    "            # 出现了之前的 index，表示找到了循环节\n",
    "            if index in recall:\n",
    "                s1cnt_prime, s2cnt_prime = recall[index]\n",
    "                # 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2\n",
    "                pre_loop = (s1cnt_prime, s2cnt_prime)\n",
    "                # 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2\n",
    "                in_loop = (s1cnt - s1cnt_prime, s2cnt - s2cnt_prime)\n",
    "                break\n",
    "            else:\n",
    "                recall[index] = (s1cnt, s2cnt)\n",
    "\n",
    "        # ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 pre_loop 和 in_loop\n",
    "        ans = pre_loop[1] + (n1 - pre_loop[0]) // in_loop[0] * in_loop[1]\n",
    "        # S1 的末尾还剩下一些 s1，我们暴力进行匹配\n",
    "        rest = (n1 - pre_loop[0]) % in_loop[0]\n",
    "        for i in range(rest):\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        ans, index = ans + 1, 0\n",
    "        # S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2\n",
    "        return ans // n2\n",
    "        '''\n",
    "        def check(fromstr, getstr):\n",
    "            i = j = 0\n",
    "            pairup = 0\n",
    "            while i < len(fromstr) and j < len(getstr):\n",
    "                if fromstr[i] == getstr[j]:\n",
    "                    pairup += 1\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            if pairup == len(getstr):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        str1 = s1 * n1\n",
    "        str2 = s2 * n2\n",
    "        m = 1\n",
    "        str3 = str2 * m\n",
    "        while check(str1, str3):\n",
    "            m += 1\n",
    "            str3 = str2 * m\n",
    "\n",
    "        return m-1\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#### 寻找循环节\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        dp=[]\n",
    "        for i in range(len(s2)):\n",
    "            start=i\n",
    "            end=0\n",
    "            for j in range(len(s1)):\n",
    "                if s1[j] == s2[start]:\n",
    "                    start+=1\n",
    "                    if start==len(s2):\n",
    "                        start=0\n",
    "                        end+=1\n",
    "            print((start,end))\n",
    "            dp.append((start,end))\n",
    "        res=0\n",
    "        next=0\n",
    "        for _ in range(n1):\n",
    "            res+=dp[next][1]\n",
    "            next=dp[next][0]\n",
    "        return res//n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        rem = {}\n",
    "        index2 = 0\n",
    "        s2loop = 0\n",
    "        s1loop = 0\n",
    "        preloop = (-1, -1)\n",
    "        loop = (-1, -1)\n",
    "        for i in range(n1):\n",
    "            for index1 in range(len(s1)):\n",
    "                if s1[index1] == s2[index2]:\n",
    "                    index2 += 1\n",
    "                    if index2 == len(s2):\n",
    "                        index2 = 0\n",
    "                        s2loop += 1\n",
    "            s1loop += 1\n",
    "            if index2 in rem:\n",
    "                preloop = rem[index2]\n",
    "                loop = (s1loop - rem[index2][0], s2loop - rem[index2][1])\n",
    "                break\n",
    "            else:\n",
    "                rem[index2] = (s1loop, s2loop)\n",
    "        \n",
    "        if s1loop == n1:\n",
    "            return s2loop // n2\n",
    "        remainloop = (n1 - preloop[0]) % loop[0]\n",
    "        ans = preloop[1] + (n1 - preloop[0]) // loop[0] * loop[1]\n",
    "        for i in range(remainloop):\n",
    "            for index1 in range(len(s1)):\n",
    "                if s1[index1] == s2[index2]:\n",
    "                    index2 += 1\n",
    "                    if index2 == len(s2):\n",
    "                        index2 = 0\n",
    "                        ans += 1\n",
    "        return ans // n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        length1 = len(s1)\n",
    "        length2 = len(s2)\n",
    "        if length2 == 1:\n",
    "            sum = 0\n",
    "            for i in range(length1):\n",
    "                if s1[i] == s2[0]:\n",
    "                    sum += 1\n",
    "            return sum * n1 // n2\n",
    "\n",
    "        m = 0\n",
    "        i = 0\n",
    "        j = 0\n",
    "\n",
    "        # 记录上次s2首字母与s1的哪个位置匹配了\n",
    "        map = {}\n",
    "        map_count = {}\n",
    "        map[0] = 0\n",
    "        map_count[0] = 0\n",
    "        while i < length1 * n1:\n",
    "            if s1[i % length1] == s2[j % length2]:  # 匹配\n",
    "                if j % length2 == length2 - 1:\n",
    "                    m += 1\n",
    "                if j != 0 and j % length2 == 0:\n",
    "                    if i % length1 in map.keys():\n",
    "                        length = i - map[i % length1]\n",
    "                        count = m - map_count[i % length1]\n",
    "                        while i <= length1 * n1 - length:\n",
    "                            i += length\n",
    "                            m += count\n",
    "                    else:\n",
    "                        map[i % length1] = i\n",
    "                        map_count[i % length1] = m\n",
    "                j += 1\n",
    "            i += 1\n",
    "\n",
    "        # print(map)\n",
    "        # print(map_count)\n",
    "        # print(m)\n",
    "        return m // n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        if n1 == 0:\n",
    "            return 0\n",
    "        s1cnt, index, s2cnt = 0, 0, 0\n",
    "        # recall 是我们用来找循环节的变量，它是一个哈希映射\n",
    "        # 我们如何找循环节？假设我们遍历了 s1cnt 个 s1，此时匹配到了第 s2cnt 个 s2 中的第 index 个字符\n",
    "        # 如果我们之前遍历了 s1cnt' 个 s1 时，匹配到的是第 s2cnt' 个 s2 中同样的第 index 个字符，那么就有循环节了\n",
    "        # 我们用 (s1cnt', s2cnt', index) 和 (s1cnt, s2cnt, index) 表示两次包含相同 index 的匹配结果\n",
    "        # 那么哈希映射中的键就是 index，值就是 (s1cnt', s2cnt') 这个二元组\n",
    "        # 循环节就是；\n",
    "        #    - 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2\n",
    "        #    - 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2\n",
    "        # 那么还会剩下 (n1 - s1cnt') % (s1cnt - s1cnt') 个 s1, 我们对这些与 s2 进行暴力匹配\n",
    "        # 注意 s2 要从第 index 个字符开始匹配\n",
    "        recall = dict()\n",
    "        while True:\n",
    "            # 我们多遍历一个 s1，看看能不能找到循环节\n",
    "            s1cnt += 1\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        s2cnt, index = s2cnt + 1, 0\n",
    "            # 还没有找到循环节，所有的 s1 就用完了\n",
    "            if s1cnt == n1:\n",
    "                return s2cnt // n2\n",
    "            # 出现了之前的 index，表示找到了循环节\n",
    "            if index in recall:\n",
    "                s1cnt_prime, s2cnt_prime = recall[index]\n",
    "                # 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2\n",
    "                pre_loop = (s1cnt_prime, s2cnt_prime)\n",
    "                # 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2\n",
    "                in_loop = (s1cnt - s1cnt_prime, s2cnt - s2cnt_prime)\n",
    "                break\n",
    "            else:\n",
    "                recall[index] = (s1cnt, s2cnt)\n",
    "\n",
    "        # ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 pre_loop 和 in_loop\n",
    "        ans = pre_loop[1] + (n1 - pre_loop[0]) // in_loop[0] * in_loop[1]\n",
    "        # S1 的末尾还剩下一些 s1，我们暴力进行匹配\n",
    "        rest = (n1 - pre_loop[0]) % in_loop[0]\n",
    "        for i in range(rest):\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        ans, index = ans + 1, 0\n",
    "        # S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2\n",
    "        return ans // n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        m, n = len(s1), len(s2)\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            j = i\n",
    "            for k in range(m):\n",
    "                if s1[k] == s2[j]:\n",
    "                    j += 1\n",
    "                if j == n:\n",
    "                    cnt += 1\n",
    "                    j = 0\n",
    "            d[i] = (cnt, j)\n",
    "\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for _ in range(n1):\n",
    "            cnt, j = d[j]\n",
    "            ans += cnt\n",
    "        return ans // n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        dic = {}\n",
    "        idx = 0\n",
    "        for _ in range(n1):\n",
    "            cnt1 += 1 \n",
    "            for c in s1:\n",
    "                if idx < len(s2) and s2[idx] == c:\n",
    "                    idx += 1 \n",
    "                    if idx == len(s2):\n",
    "                        cnt2 += 1 \n",
    "                        idx = 0 \n",
    "            if idx in dic:\n",
    "                pre = dic[idx]\n",
    "                loop = [cnt1 - pre[0], cnt2 - pre[1]]\n",
    "                break\n",
    "            dic[idx] = [cnt1, cnt2]\n",
    "            if cnt1 == n1:\n",
    "                return cnt2 // n2\n",
    "        \n",
    "        res = pre[1] + (n1 - pre[0]) // loop[0] * loop[1]\n",
    "        rest = (n1 - pre[0]) % loop[0]\n",
    "        for _ in range(rest):\n",
    "            for c in s1:\n",
    "                if idx < len(s2) and s2[idx] == c:\n",
    "                    idx += 1 \n",
    "                    if idx == len(s2):\n",
    "                        res += 1 \n",
    "                        idx = 0 \n",
    "        return res // n2\n",
    "\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        dic = {} \n",
    "        idx = 0\n",
    "        for _ in range(n1):\n",
    "            cnt1 += 1\n",
    "            for i in range(len(s1)):\n",
    "                if s2[idx] == s1[i]:\n",
    "                    idx += 1 \n",
    "                    if idx == len(s2):\n",
    "                        cnt2 += 1 \n",
    "                        idx = 0\n",
    "            if idx in dic:\n",
    "                pre = dic[idx]\n",
    "                loop = [cnt1 - pre[0], cnt2 - pre[1]]\n",
    "                break \n",
    "            dic[idx] = [cnt1, cnt2]\n",
    "            if cnt1 == n1:\n",
    "                return cnt2 // n2 \n",
    "        res = pre[1] + (n1 - pre[0]) // loop[0] * loop[1]\n",
    "        rest = (n1 - pre[0]) % loop[0]\n",
    "        for _ in range(rest):\n",
    "            for i in range(len(s1)):\n",
    "                if s2[idx] == s1[i]:\n",
    "                    idx += 1 \n",
    "                    if idx == len(s2):\n",
    "                        res += 1 \n",
    "                        idx = 0\n",
    "        return res // n2 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        n = len(s2)\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            j = i\n",
    "            for k, c in enumerate(s1):\n",
    "                if c == s2[j]:\n",
    "                    j += 1\n",
    "                if j == n:\n",
    "                    cnt += 1\n",
    "                    j = 0\n",
    "            d[i] = (cnt, j)\n",
    "\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for _ in range(n1):\n",
    "            cnt, j = d[j]\n",
    "            ans += cnt\n",
    "        return ans // n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "\n",
    "        len1, len2 = len(s1), len(s2)\n",
    "        index1, index2 = 0, 0\n",
    "\n",
    "        if len1 == 0 or len2 == 0 or len1 * n1 < len2 * n2:\n",
    "            return 0\n",
    "\n",
    "        map1, map2 = {}, {}\n",
    "        ans = 0\n",
    "\n",
    "        while index1 // len1 < n1:\n",
    "            if index1 % len1 == len1 - 1:\n",
    "                if index2 % len2 in map1:\n",
    "                    cycle_len = index1 // len1 - map1[index2 % len2] // len1\n",
    "                    cycle_num = (n1 - 1 - index1 // len1) // cycle_len\n",
    "                    cycle_s2_num = index2 // len2 - map2[index2 % len2] // len2\n",
    "\n",
    "                    index1 += cycle_num * cycle_len * len1\n",
    "                    ans += cycle_num * cycle_s2_num\n",
    "                else:\n",
    "                    map1[index2 % len2] = index1\n",
    "                    map2[index2 % len2] = index2\n",
    "\n",
    "            if s1[index1 % len1] == s2[index2 % len2]:\n",
    "                if index2 % len2 == len2 - 1:\n",
    "                    ans += 1\n",
    "                index2 += 1\n",
    "            index1 += 1\n",
    "        return ans // n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        dp=[]\n",
    "        for i in range(len(s2)):\n",
    "            start=i\n",
    "            r=0\n",
    "            for j in range(len(s1)):\n",
    "                if s2[start]==s1[j]:\n",
    "                    start+=1\n",
    "                    if start==len(s2):\n",
    "                        r+=1\n",
    "                        start=0\n",
    "            dp.append([start,r])\n",
    "        res=0\n",
    "        end=0\n",
    "        for _ in range(n1):\n",
    "            res+=dp[end][1]\n",
    "            end=dp[end][0]\n",
    "\n",
    "\n",
    "        return res//n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        dic = {}\n",
    "        idx = 0\n",
    "        for _ in range(n1):\n",
    "            cnt1 += 1 \n",
    "            for c in s1:\n",
    "                if idx < len(s2) and s2[idx] == c:\n",
    "                    idx += 1 \n",
    "                    if idx == len(s2):\n",
    "                        cnt2 += 1 \n",
    "                        idx = 0 \n",
    "            if idx in dic:\n",
    "                pre = dic[idx]\n",
    "                loop = [cnt1 - pre[0], cnt2 - pre[1]]\n",
    "                break\n",
    "            dic[idx] = [cnt1, cnt2]\n",
    "            if cnt1 == n1:\n",
    "                return cnt2 // n2\n",
    "        \n",
    "        res = pre[1] + (n1 - pre[0]) // loop[0] * loop[1]\n",
    "        rest = (n1 - pre[0]) % loop[0]\n",
    "        for _ in range(rest):\n",
    "            for c in s1:\n",
    "                if idx < len(s2) and s2[idx] == c:\n",
    "                    idx += 1 \n",
    "                    if idx == len(s2):\n",
    "                        res += 1 \n",
    "                        idx = 0 \n",
    "        return res // n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        list2 = list(s2)\n",
    "        setlist2 = set(list2)\n",
    "        list1 = []\n",
    "        for char in s1:\n",
    "            if char not in setlist2:\n",
    "                continue\n",
    "            list1.append(char)\n",
    "        index = 0\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        recall = {}\n",
    "        while True:\n",
    "            for char in list1:\n",
    "                if char == list2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(list2):\n",
    "                        index = 0\n",
    "                        cnt2 += 1\n",
    "            cnt1 += 1\n",
    "            if cnt1 == n1:\n",
    "                return cnt2 // n2\n",
    "            \n",
    "            if index in recall:\n",
    "                precnt1, precnt2 = recall[index]\n",
    "                preloop = (precnt1, precnt2)\n",
    "                loop = (cnt1 - precnt1, cnt2 - precnt2)\n",
    "                break\n",
    "            else:\n",
    "                recall[index] = (cnt1, cnt2)\n",
    "        \n",
    "        ans = preloop[1] + (n1 - preloop[0]) // loop[0] * loop[1]\n",
    "        rest = (n1 - preloop[0]) % loop[0]\n",
    "\n",
    "        for i in range(rest):\n",
    "            for char in list1:\n",
    "                if char == list2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(list2):\n",
    "                        index = 0\n",
    "                        ans += 1\n",
    "        return ans // n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "\n",
    "        len1, len2 = len(s1), len(s2)\n",
    "        index1, index2 = 0, 0\n",
    "\n",
    "        if len1 == 0 or len2 == 0 or len1 * n1 < len2 * n2:\n",
    "            return 0\n",
    "\n",
    "        map1, map2 = {}, {}\n",
    "        ans = 0\n",
    "\n",
    "        while index1 // len1 < n1:\n",
    "            if index1 % len1 == len1 - 1:\n",
    "                if index2 % len2 in map1:\n",
    "                    cycle_len = (index1 - map1[index2 % len2]) // len1\n",
    "                    cycle_num = (n1 - (index1 + 1) // len1) // cycle_len\n",
    "                    cycle_s2_num = (index2 - map2[index2 % len2]) // len2\n",
    "\n",
    "                    index1 += cycle_num * cycle_len * len1\n",
    "                    ans += cycle_num * cycle_s2_num\n",
    "                else:\n",
    "                    map1[index2 % len2] = index1\n",
    "                    map2[index2 % len2] = index2\n",
    "\n",
    "            if s1[index1 % len1] == s2[index2 % len2]:\n",
    "                if index2 % len2 == len2 - 1:\n",
    "                    ans += 1\n",
    "                index2 += 1\n",
    "            index1 += 1\n",
    "        return ans // n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n",
    "        if n1 == 0:\n",
    "            return 0\n",
    "        s1cnt, index, s2cnt = 0, 0, 0\n",
    "        # recall 是我们用来找循环节的变量，它是一个哈希映射\n",
    "        # 我们如何找循环节？假设我们遍历了 s1cnt 个 s1，此时匹配到了第 s2cnt 个 s2 中的第 index 个字符\n",
    "        # 如果我们之前遍历了 s1cnt' 个 s1 时，匹配到的是第 s2cnt' 个 s2 中同样的第 index 个字符，那么就有循环节了\n",
    "        # 我们用 (s1cnt', s2cnt', index) 和 (s1cnt, s2cnt, index) 表示两次包含相同 index 的匹配结果\n",
    "        # 那么哈希映射中的键就是 index，值就是 (s1cnt', s2cnt') 这个二元组\n",
    "        # 循环节就是；\n",
    "        #    - 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2\n",
    "        #    - 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2\n",
    "        # 那么还会剩下 (n1 - s1cnt') % (s1cnt - s1cnt') 个 s1, 我们对这些与 s2 进行暴力匹配\n",
    "        # 注意 s2 要从第 index 个字符开始匹配\n",
    "        recall = dict()\n",
    "        while True:\n",
    "            # 我们多遍历一个 s1，看看能不能找到循环节\n",
    "            s1cnt += 1\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        s2cnt, index = s2cnt + 1, 0\n",
    "            # 还没有找到循环节，所有的 s1 就用完了\n",
    "            if s1cnt == n1:\n",
    "                return s2cnt // n2\n",
    "            # 出现了之前的 index，表示找到了循环节\n",
    "            if index in recall:\n",
    "                s1cnt_prime, s2cnt_prime = recall[index]\n",
    "                # 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2\n",
    "                pre_loop = (s1cnt_prime, s2cnt_prime)\n",
    "                # 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2\n",
    "                in_loop = (s1cnt - s1cnt_prime, s2cnt - s2cnt_prime)\n",
    "                break\n",
    "            else:\n",
    "                recall[index] = (s1cnt, s2cnt)\n",
    "\n",
    "        # ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 pre_loop 和 in_loop\n",
    "        ans = pre_loop[1] + (n1 - pre_loop[0]) // in_loop[0] * in_loop[1]\n",
    "        # S1 的末尾还剩下一些 s1，我们暴力进行匹配\n",
    "        rest = (n1 - pre_loop[0]) % in_loop[0]\n",
    "        for i in range(rest):\n",
    "            for ch in s1:\n",
    "                if ch == s2[index]:\n",
    "                    index += 1\n",
    "                    if index == len(s2):\n",
    "                        ans, index = ans + 1, 0\n",
    "        # S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2\n",
    "        return ans // n2\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
